﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Emerald
{
    public class Board
    {
        private readonly BoardArray data = new BoardArray();

        public BoardArray BoardArray
        {
            get { return data; }
        }

        public Board()
        {
            for (byte x = 8; x < 8 + 5; x++)
                for (byte y = 8; y < 8 + 4; y++)
                {
                    data[x, y] = new Tile(x, y);
                }
#if DEBUG
            Random rand = new Random();
            EColor color = EColor.Red;

            for (int i = 0; i < 12; i++)
            {
                Tile t = data[(byte)rand.Next(8, 13), (byte)rand.Next(8, 12)];

                if (t.Piece == null)
                {
                    t.Piece = new Piece(color);
                    color = color.Opposite();
                }
                else
                {
                    i--;
                }
            }
#endif
        }

        public Board(Board b)
        {
            foreach (Tile tile in b.BoardArray.Tiles)
            {
                this.BoardArray[tile.Location] = new Tile(tile.Location);
                if (tile.Piece != null)
                {
                    Piece p = new Piece(tile.Piece.Color);
                    if (tile.Piece.State == EState.Marked)
                        p.Flip();
                    this.BoardArray[tile.Location].Piece = p;
                }
            }
        }

        public Board(string boardString)
        {
            int strCount = 0;
            for (byte i = 0; i < 21; i++)
            {
                for (byte j = 0; j < 20; j++)
                {
                    BoardPoint bp = new BoardPoint(i, j);
                    Tile t = null;
                    char str = boardString[strCount];
                    strCount++;
                    if (str != ' ')
                    {
                        t = new Tile(bp);

                        if (str == 'r' || str == 'R')
                        {
                            t.Piece = new Piece(EColor.Red);
                            if (str == 'R')
                                t.Piece.Flip();
                        }

                        if (str == 'w' || str == 'W')
                        {
                            t.Piece = new Piece(EColor.White);
                            if (str == 'W')
                                t.Piece.Flip();
                        }
                    }

                    if (t != null)
                        BoardArray[bp] = t;
                }
            }

        }


        public bool PerformActionWithoutRules(Action a)
        {
            if (false == a.AddingPiece)
            {
                if (a.MovingTile)
                {
                    MoveTile(a.OldTilePosition.Value, a.NewPiecePosition);
                }

                MovePiece(a.OldPiecePosition.Value, a.NewPiecePosition);

                int euclidianDistanceTo = (int)a.OldPiecePosition.Value.EuclidianDistanceTo(a.NewPiecePosition);
                if (2 == euclidianDistanceTo)
                {
                    data[a.NewPiecePosition].Piece.Flip();
                }
            }
            else
            {
                data[a.NewPiecePosition].Piece = new Piece(a.NewPieceColor.Value);
            }

            return true;
        }

        public bool PerformAction(Action a)
        {
            bool legal = isActionLegal(a);
            if (!legal) return false;
            bool performActionWithoutRules = PerformActionWithoutRules(a);
            return legal && performActionWithoutRules;
        }

        private bool isActionLegal(Action a)
        {
            if (a.AddingPiece)
            {
                return data[a.NewPiecePosition] != null && data[a.NewPiecePosition].Piece == null;
            }

            int euclidianDistanceTo = (int)a.OldPiecePosition.Value.EuclidianDistanceTo(a.NewPiecePosition);

            // Jumping step size may not be larger than two
            if (euclidianDistanceTo > 2)
                return false;
            // Walking step size may not be smaller than zero
            if (euclidianDistanceTo < 1)
                return false;

            // Jumping should happen in a horizontal, vertical or diagonal direction
            if (a.JumpingPiece)
            {

                if (a.OldPiecePosition.Value.ManhattanDistanceTo(a.NewPiecePosition) % 2 == 1)
                    return false;

                sbyte halfDX = (sbyte)((a.NewPiecePosition.X - a.OldPiecePosition.Value.X) / 2);
                sbyte halfDY = (sbyte)((a.NewPiecePosition.Y - a.OldPiecePosition.Value.Y) / 2);

                if (false == data.IsFilledTile(a.OldPiecePosition.Value, halfDX, halfDY) ^ (data.IsFilledTile(a.OldPiecePosition.Value, halfDX, halfDY) && data[(byte)(a.OldPiecePosition.Value.X + halfDX), (byte)(a.OldPiecePosition.Value.Y + halfDY)].Piece == null))
                    return false;
            }

            // The tile we're coming from, must contain a piece, so that we can move it 
            if(a.OldPiecePosition.HasValue && data[a.OldPiecePosition.Value]!=null)
            if (data[a.OldPiecePosition.Value].Piece == null)
                return false;


            if (false == a.MovingTile)
            {
                // Since we're not moving a tile, there should be a tile on the new piece position...
                if (data[a.NewPiecePosition] == null)
                    return false;
                // ...but that should not contain a piece already
                if (data[a.NewPiecePosition].Piece != null)
                    return false;
            }
            else
            {
                //We're moving a tile, so there shouldn't be a tile on the new piece position
                if (data[a.NewPiecePosition] != null)
                    return false;

                // The tile should have at least two free side before movement
                Tile[] neighbours = data.GetNeighboursOf(a.OldTilePosition.Value, a.OldTilePosition.Value);
                if (neighbours.Count(t => t != null) > 2)
                    return false;

                //check if neighbours are stil valid
                for (int i = 0; i < neighbours.Length; i++)
                    if (neighbours[i] != null)
                        if(!(data.GetNeighboursOf(neighbours[i].Location, a.OldPiecePosition.Value).Count(t => t != null)-1 > 0))
                            return false;
                
                // The tile should have at least touch one side of the tile cluster
                if (data.GetNeighboursOf(a.NewPiecePosition, a.OldTilePosition.Value).Count(t => t != null) == 0)
                    return false;

                //DisjointSet ds = new DisjointSet(data.Tiles, a.NewPiecePosition);
                //foreach (Tile tile in data.Tiles)
                //{
                //    foreach (Tile tile2 in data.GetNeighboursOf(tile.Location, a.OldTilePosition.Value))
                //    {
                //        ds.UnionElementsSets(tile.Location.AsIndex, tile2.Location.AsIndex);
                //    }
                //}
                //List<Tile> neighboursOfNewPiecePosition = data.GetNeighboursOf(a.NewPiecePosition, a.OldTilePosition.Value).ToList();
                //foreach (Tile tile2 in neighboursOfNewPiecePosition)
                //{
                //    ds.UnionElementsSets(tile2.Location.AsIndex, a.NewPiecePosition.AsIndex);
                //}

                //if (ds.Roots > 1)
                //    return false;
            }

            return true;
        }

        private class DisjointSet
        {
            readonly Dictionary<int, int> array = new Dictionary<int, int>();


            public DisjointSet(IEnumerable<Tile> tiles, params BoardPoint[] others)
            {
                foreach (Tile tile in tiles)
                    array[tile.Location.AsIndex] = -1;
                foreach (BoardPoint bp in others)
                    array[bp.AsIndex] = -1;
            }

            public int Roots
            {
                get
                {
                    return array.Count(a => a.Value < 0);
                }
            }

            /**
             *  Union() unites two disjoint sets into a single set.  A Union-by-rank
             *  heuristic is used to choose the new root.  This method will corrupt
             *  the data structure if root1 and root2 are not roots of their respective
             *  sets, or if they're identical.
             *
             *  @param root1 the root of the first set.
             *  @param root2 the root of the other set.
             **/
            public void Union(int root1, int root2)
            {
                if (array[root2] < array[root1])
                {
                    array[root1] = root2;             // root2 is taller; make root2 new root
                }
                else
                {
                    if (array[root1] == array[root2])
                    {
                        array[root1]--;            // Both trees same height; new one is taller
                    }
                    array[root2] = root1;       // root1 equal or taller; make root1 new root
                }
            }

            public void UnionElementsSets(int el1, int el2)
            {
                int root1 = Find(el1);
                int root2 = Find(el2);
                if (root1 != root2)
                    Union(root1, root2);
            }

            /**
             *  Find() finds the (int) name of the set containing a given element.
             *  Performs path compression along the way.
             *
             *  @param x the element sought.
             *  @return the set containing x.
             **/
            public int Find(int x)
            {
                if (IsRoot(x))
                {
                    return x;                         // x is the root of the tree; return it
                }
                else
                {
                    // Find out who the root is; compress path by making the root x's parent.
                    return array[x] = Find(array[x]);                                       // Return the root
                }
            }

            public bool IsRoot(int x)
            {
                return array[x] < 0;
            }
        }

        public void MoveTile(BoardPoint from, BoardPoint to)
        {
            if (BoardArray[from] != null && BoardArray[to] == null)
            {
                BoardArray[to] = BoardArray[from];
                BoardArray[from] = null;
                if (BoardChanged != null)
                    BoardChanged(this, from, to);
            }
        }

        public event GameState.BoardChangedEvent BoardChanged;

        public void MovePiece(BoardPoint from, BoardPoint to)
        {
            if (BoardArray[from].Piece != null && BoardArray[to].Piece == null)
            {
                BoardArray[to].Piece = BoardArray[from].Piece;
                BoardArray[from].Piece = null;
            }
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            sb.Append("   |");
            for (byte x = data.TopLeftBoundary.X; x <= data.BottomRightBoundary.X; x++)
            {
                sb.AppendFormat(" {0:00}|", x);
            }
            sb.AppendLine();


            for (byte y = data.TopLeftBoundary.Y; y <= data.BottomRightBoundary.Y; y++)
            {
                sb.AppendFormat("{0:00} |", y);
                for (byte x = data.TopLeftBoundary.X; x <= data.BottomRightBoundary.X; x++)
                {
                    Tile tile = data[x, y];
                    if (tile != null)
                    {
                        if (tile.Piece != null)
                        {
                            char name = Enum.GetName(typeof(EColor), tile.Piece.Color)[0];
                            if (tile.Piece.State == EState.Marked)
                                name = char.ToUpper(name);
                            else
                                name = char.ToLower(name);
                            sb.AppendFormat(" {0} ", name);
                        }
                        else
                            sb.Append("   ");
                    }
                    else
                        sb.Append("###");

                    sb.Append('|');
                }
                sb.AppendLine();
            }

            return sb.ToString();
        }

        internal EColor? IsWonByPlayer()
        {
            EColor? color;

            // horizontal
            for (byte y = data.TopLeftBoundary.Y; y < data.TopLeftBoundary.Y + data.BottomRightBoundary.Y; y++)
                for (byte x = data.TopLeftBoundary.X; x < data.TopLeftBoundary.X + data.BottomRightBoundary.X - 4; x++)
                {
                    color = data.GetColor(x, y);
                    if (color == null) continue;

                    if (data.ContainsMarkedPiece(x, y, color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 1)), y, color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 2)), y, color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 3)), y, color.Value))
                        return color.Value;
                }

            // vertical
            for (byte x = data.TopLeftBoundary.X; x < data.TopLeftBoundary.X + data.BottomRightBoundary.X; x++)
                for (byte y = data.TopLeftBoundary.Y; y < data.TopLeftBoundary.Y + data.BottomRightBoundary.Y - 4; y++)
                {
                    color = data.GetColor(x, y);
                    if (color == null) continue;

                    if (data.ContainsMarkedPiece(x, y, color.Value) &&
                        data.ContainsMarkedPiece(x, (byte)((y + 1)), color.Value) &&
                        data.ContainsMarkedPiece(x, (byte)((y + 2)), color.Value) &&
                        data.ContainsMarkedPiece(x, (byte)((y + 3)), color.Value))
                        return color;
                }

            // diagonal
            for (byte x = data.TopLeftBoundary.X; x < data.TopLeftBoundary.X + data.BottomRightBoundary.X - 4; x++)
                for (byte y = data.TopLeftBoundary.Y; y < data.TopLeftBoundary.Y + data.BottomRightBoundary.Y - 4; y++)
                {
                    // top-down     \
                    color = data.GetColor(x, y);
                    if (color == null) continue;

                    if (data.ContainsMarkedPiece(x, y, color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 1)), (byte)((y + 1)), color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 2)), (byte)((y + 2)), color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 3)), (byte)((y + 3)), color.Value))
                        return color;

                    // bottom-up    /
                    if (data.ContainsMarkedPiece(x, y, color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 1)), (byte)((y - 1)), color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 2)), (byte)((y - 2)), color.Value) &&
                        data.ContainsMarkedPiece((byte)((x + 3)), (byte)((y - 3)), color.Value))
                        return color;
                }

            // no winner
            return null;
        }
    }
}
